package com.zjsru.plan2024.normal;

import java.util.Arrays;

/**
 * 2549. 统计桌面上的不同数字
 * 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
 * 然后，将这些数字放在桌面上。
 * @Author: cookLee
 * @Date: 2024-03-24
 */
public class DistinctIntegers {

    /**
     * 主
     * \
     * 输入：n = 5
     * 输出：4
     * 解释：最开始，5 在桌面上。
     * 第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。
     * 再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。
     * 在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。
     * \
     * 输入：n = 3
     * 输出：2
     * 解释：
     * 因为 3 % 2 == 1 ，2 也出现在桌面上。
     * 在十亿天结束时，桌面上的不同数字只有两个：2 和 3
     * \
     * @param args args
     */
    public static void main(String[] args) {
        DistinctIntegers distinctIntegers = new DistinctIntegers();
        int n = 5;
        System.out.println(distinctIntegers.distinctIntegers(n));
    }

    /**
     * 不同整数
     * 返回不同的数字且数字会一直保留到结束，相当于直接遍历即可
     * @param n n
     * @return int
     */
    public int distinctIntegers(int n) {
        //记录桌面上已经出现的正整数
        int[] nums = new int[n + 1];
        //一开始只出现一个数字
        nums[n] = 1;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i <= n; i++) {
                if (nums[i] == 0) {
                    continue;
                }
                for (int j = 1; j <= n; j++) {
                    if (i % j == 1) {
                        nums[j] = 1;
                    }
                }
            }
        }
        return Arrays.stream(nums).sum();
    }

}
